/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  // 排序是剪枝的前提
  candidates = candidates.sort((a, b) => a - b);
  let result = [], temp = [];
  function dfs(remain, begin) {
    if(remain === 0) {
      result.push([...temp]);
      return;
    }

    for(let i = begin; i < candidates.length; i++) {
      if(remain - candidates[i] >= 0) {
        temp.push(candidates[i]);
        dfs(remain - candidates[i], i);
        temp.splice(temp.length - 1, 1);
      }
    }
  }


  dfs(target, 0);
  return result;
};
let candidates = [2,3,6,7], target = 7;
console.log(combinationSum(candidates, target));
candidates = [2,3,5], target = 8;
console.log(combinationSum(candidates, target));
candidates = [2], target = 1;
console.log(combinationSum(candidates, target));
